package com.dexter.year2023.charpter1_linkedlist.level3.topic3_1环的入口;

import java.util.HashSet;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;

/**
 * LeetCode 141. 环形链表
 * https://leetcode.cn/problems/linked-list-cycle/
 * <p>
 * 给你一个链表的头结点 head ，判断链表中是否有环。
 * 如果链表中有某个结点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
 * 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
 * <p>
 * 示例 1：
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个结点。
 * 示例 2：
 * 输入：head = [1,2], pos = 0
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第一个结点。
 * 示例 3：
 * 输入：head = [1], pos = -1
 * 输出：false
 * 解释：链表中没有环。
 * <p>
 * 提示：
 * 链表中结点的数目范围是 [0, 104]
 * -105 <= Node.val <= 105
 * pos 为 -1 或者链表中的一个 有效索引 。
 * <p>
 * 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
 *
 * @author Dexter
 */
public class Demo1HasCycle {
    /**
     * 判断链表是否有环
     */
    public static void main(String[] args) {
        int[] a = {3, 2, 0, -4};
        int pos = 1;
        // 构造类型：普通/有环
        int nodeType = 2;
        Node head = null;
        switch (nodeType) {
            case 1:
                head = initLinkedList(a);
                break;
            case 2:
                head = initLinkedListHasCycle(a, pos);
                break;
            default:
                System.out.println("构造类型超出范围");
                break;
        }

        // 测试方法
        int testMethod = 2;
        boolean res = false;
        switch (testMethod) {
            case 1:
                res = hasCycleByHashSet(head);
                break;
            case 2:
                // 进阶：双指针实现，O(1)内存
                res = hasCycleByTwoPoints(head);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        System.out.println(res ? "有环" : "无环"); // 有环链表是否能打印？
    }

    /**
     * 构造有环链表
     *
     * @param array
     * @param pos   入口预设位置
     * @return
     */
    public static Node initLinkedListHasCycle(int[] array, int pos) {
        Node head = null, cur = null;
        Node cross = null;
        for (int i = 0; i < array.length; i++) {
            // 创建新结点
            Node newNode = new Node(array[i]);
            newNode.next = null;
            if (i == 0) {
                head = newNode;
                cur = head;
            } else {
                cur.next = newNode;
                cur = newNode;
                // 预设入口位置【重点】
                if (i == pos) {
                    cross = cur;
                }
            }
        }
        // 尾结点接cross
        cur.next = cross;
        return head;
    }

    /**
     * 法1：用HashSet判断
     *
     * @param head
     * @return
     */
    private static boolean hasCycleByHashSet(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return false;
        }
        // 初始化
        HashSet<Node> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 法2：用快慢指针，有环终会相遇
     *
     * @param head
     * @return
     */
    private static boolean hasCycleByTwoPoints(Node head) {
        // 判空
        if (head == null || head.next == null) {
            return false;
        }
        // 初始化
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}
